package top.kiterunner.learning.moon_test;

/**
 * AdorynZhao in Tencent-UESTC.
 * Source Code Created on 2017/7/14.
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] num = {6,3,7,1,4,5};
        heapSort(num);
        for(int i : num)
            System.out.print(i);
    }
    public static void heapSort(int[] num) {
        if(num == null || num.length == 0) return;
        int len = num.length - 1;
        for(int i = (len -1)/2; i>=0; i--)
            heapAdjust(num, i, len);
        for(int i = len; i > 0; i--) {
            exch(num, 0, i);
            heapAdjust(num, 0, i-1);
        }
    }
    public static void heapAdjust(int[] num, int i, int len) {
        int temp = num[i];
        for(int j = 2 * i +1; j <= len; j = j * 2 + 1) {
            if(j + 1 <= len && num[j+1] > num[j]) j++;
            if(temp >= num[j]) break;
            num[i] = num[j];
            i = j;
        }
        num[i] = temp;
    }
    public static void exch(int[] num, int i, int j){
        int trf = num[i];
        num[i] = num[j];
        num[j] = trf;
    }
}